#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int countArrangement(int n) {
        int count = 0;
        vector<bool> used(n + 1, false);
        backtrack(n, count, used, 1);
        return count;
    }
private:
    void backtrack(int n, int& count, vector<bool>& used, int index) {
        if (index > n) { count++; return; }
        for (int num = 1; num <= n; num++) {
            if (!used[num] && (index % num == 0 || num % index == 0)) {
                used[num] = true;
                backtrack(n, count, used, index + 1);
                used[num] = false;
            }
        }
    }
};